Multipliers are special purpose circuits within a microprocessor or digital signal processor used to perform the product of a multiplicand and multiplier. In a typical multiplier, partial products are formed by multiplying a binary representation (which may for example be binary, two's-complement, or one's-complement form) of the multiplicand times a binary representation of the multiplier to form a two-dimensional array of partial products. The partial products are reduced, that is added together to obtain a binary representation of the product.
The partial products may be reduced in any of several known methods. With the least significant bit (LSB) of the the multiplicand and multiplier on the right, the LSB of the product will also be on the right. The conventional way to reduce partial products is to start at the right and proceed to the left (right-to-left or LSB first) with carries being shifted, or propagated, to the left. Operations reducing partial products and carry propagation are repetitive. Reduction schemes vary in complexity from a straight-forward linear reduction to Wallace's logarithmic reduction.
In a typical right-to-left carry-save multiplier, the partial products are reduced starting at the top of the array of partial products and working toward the bottom of the array. The least significant part of the final partial-product terms are generated in binary form whereas the most significant part is generated in carry-save form. The bits in the most significant part arrive simultaneously. A carry-propagate adder is used to convert them from carry-save form to binary form to complete the multiplication operation. The delay of a fast carry-propagate adder may be a significant portion of the total multiplier delay.
Left-to-right multipliers are significantly faster than right-to-left multipliers because they do not require a carry-propagate adder for the more significant partial products to complete the multiplication process. The most significant partial product terms are available in carry-save form earlier than in conventional right-to-left multipliers. The carry and sum bits in the more significant part of the final partial products do not arrive simultaneously. They are skewed with the more significant bits arriving earlier. Left-to-right multipliers exploit this property to significantly improve the speed of the multiplier.
An example of left-to-right multiplier is disclosed in a paper entitled "Fast Multiplication Without Carry Propagate Addition" by M. D. Ercegovac and T. Lang published in the IEEE Transactions on Computers, November 1990, pages 1385-1390, the disclosure of which is hereby incorporated by reference.
The left-to-right or most significant bit first (MSB first) multiplier was extended to a full word width multiplier that produces the least significant part of the product in binary form and uses a converter to convert the most significant part from carry-save to binary form is disclosed in a paper entitled "Carry-save multiplication schemes without final addition," by L. Cimininera and P. Montuschi published in the IEEE Transactions on Computers, September 1996, pages 1050-1055, the disclosure of which is hereby incorporated by reference. In the disclosed converter, only one of the two conditional forms described in the Ercegovac and Lang paper is used along with control signals that determine if a particular digit should be incremented. This technique requires a final stage that operates on the digit based on control signals.
Increasing clock frequencies, concomitantly shortening clock periods, necessitates increasing multiplier efficiency. While the left-to-right carry-free multiplier has improved the efficiency of multipliers by reducing hardware requirements and time of calculating a final product, there remains a need to further reduce the time required to perform a multiplication operation, such as for multiplication intense operations in digital signal processors.